// https://leetcode.cn/problems/reorder-list/description/

// 算法思路总结：
// 1. 使用快慢指针找到链表中点并断开
// 2. 反转后半部分链表
// 3. 合并前半部分和反转后的后半部分链表
// 5. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include "LinkedListUtils.h"

class Solution 
{
public:
    void reorderList(ListNode* head) 
    {
        // 1.先找中间节点并断开连接
        ListNode* slow = head, *fast = head;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* cur1 = head, *cur2 = slow->next;
        slow->next = nullptr;

        // 2.接着倒序后一个链表
        ListNode* dummy1 = new ListNode(-1);
        while (cur2)
        {
            ListNode* next = cur2->next;
            cur2->next = dummy1->next;
            dummy1->next = cur2;
            cur2 = next;
        }
        cur2 = dummy1->next;

        // 3.接着开始遍历两条链表并合并
        ListNode* dummy2 = new ListNode(-1);
        ListNode* cur = dummy2;
        while (cur1 || cur2)
        {
            if (cur1)
            {
                cur->next = cur1;
                cur = cur1;
                cur1 = cur1->next;
            }
            if (cur2)
            {
                cur->next = cur2;
                cur = cur2;
                cur2 = cur2->next;
            }
        }
    }
};

int main()
{
    vector<int> v1 = {1,2,3,4}, v2 = {1,2,3,4,5};
    auto l1 = createLinkedList(v1), l2 = createLinkedList(v2);

    Solution sol;
    sol.reorderList(l1);
    sol.reorderList(l2);

    printLinkedList(l1);
    printLinkedList(l2);

    return 0;
}